package com.demo.java.OD51_100.OD77;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【计算网络信号】问题-贪心算法
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145620689
 */
public class OdMain {
    // 使用 LinkedList 来存储每个待处理的区块
    public static final LinkedList<BlockModel> linkedList = new LinkedList<>();
    // 定义四个方向：上、下、左、右
    public static final int[][] dicArray = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * 扩展传播的逻辑
     *
     * @param matrix 避免重复访问的矩阵
     * @param x      当前的x坐标
     * @param y      当前的y坐标
     * @param d      当前的距离
     */
    private static void diffusive(int[][] matrix, int x, int y, int d) {
        // 遍历四个方向
        for (int[] di : dicArray) {
            int newX = x + di[0], newY = y + di[1];

            // 检查新坐标是否合法
            if (newY >= 0 && newY < matrix[0].length && newX >= 0 && newX < matrix.length) {
                int next = matrix[newX][newY];

                // 如果新坐标未被访问过并且是0，设置为当前距离 - 1
                if (next == 0) {
                    matrix[newX][newY] = d - 1;
                }

                // 如果当前距离大于2并且没有被访问过，则继续扩展
                if (d > 2 && next != -1) {
                    linkedList.add(new BlockModel(newX, newY, d - 1));
                }
            }
        }
    }

    // BlockModel 用于保存每个节点的坐标以及当前的距离
    private static class BlockModel {
        int x;
        int y;
        int d;

        public BlockModel(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }

        @Override
        public String toString() {
            return "BlockModel [x=" + x + ", y=" + y + ", d=" + d + "]";
        }
    }

    public static void main(String[] args) {
        try {
            // 初始化 Scanner 以读取输入
            Scanner s = new Scanner(System.in);

            // 读取矩阵的维度
            int m = s.nextInt();  // 行数
            int n = s.nextInt();  // 列数

            // 初始化矩阵
            int[][] matrixArray = new int[m][n];
            int[] start = new int[2];
            int[] end = new int[2];

            // 读取矩阵数据
            for (int x = 0; x < m; x++) {
                for (int y = 0; y < n; y++) {
                    matrixArray[x][y] = s.nextInt();

                    // 记录起点的位置
                    if (matrixArray[x][y] > 0) {
                        start[0] = x;
                        start[1] = y;
                    }
                }
            }

            // 读取终点坐标
            end[0] = s.nextInt();
            end[1] = s.nextInt();

            // 将起点放入队列
            linkedList.add(new BlockModel(start[0], start[1], matrixArray[start[0]][start[1]]));

            // 开始进行扩散处理
            while (!linkedList.isEmpty()) {
                // 获取队列中最前面的元素
                BlockModel block = linkedList.pollFirst();
                // 进行扩散操作
                diffusive(matrixArray, block.x, block.y, block.d);
            }

            // 输出终点的值，即到达终点的最小步数
            System.out.print(matrixArray[end[0]][end[1]]);
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");
        }
    }

}